import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 */
class ThreeSum {

    public static void main(String[] args) {
        //List<List<Integer>> result = threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        List<List<Integer>> result = threeSum(new int[]{-2,0,1,1,2});
        //List<List<Integer>> result = threeSum(new int[]{0, 0, 0});
        //List<List<Integer>> result = threeSumBySort(new int[]{-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0});
        for (List<Integer> integers : result) {
            for (Integer integer : integers) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }

    /**
     * 使用map和set
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSumFor2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 0) return result;
        Set<String> same = new HashSet();
        Set<Integer> numSet = new HashSet();
        Map<Integer, Integer> repeatSet = new HashMap<>();
        for (int num : nums) {
            if (numSet.contains(num)) {
                if (repeatSet.get(num) == null) {
                    repeatSet.put(num, 1);
                }
                repeatSet.put(num, repeatSet.get(num) + 1);
            } else {
                numSet.add(num);
            }
        }
        for (int i = 0; i <= nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                int want = -nums[i] - nums[j];
                if (numSet.contains(want)) {
                    //判断want是不是本身且和ij不一样
                    if (want != nums[i] && want != nums[j]) {
                    } else if (want == nums[i] && want == nums[j]) {
                        if (repeatSet.get(want) < 3) continue;
                    } else {
                        if (!repeatSet.containsKey(want)) continue;
                    }
                    String key = min(nums[i], nums[j], want) + "-" + max(nums[i], nums[j], want);
                    if (!same.contains(key)) {
                        same.add(key);
                        List<Integer> integers = new ArrayList<>();
                        integers.add(nums[i]);
                        integers.add(nums[j]);
                        integers.add(want);
                        result.add(integers);
                    }
                }
            }
        }
        return result;
    }

    private static int min(int a, int b, int c) {
        if (a < b) return a < c ? a : c;
        else return b < c ? b : c;
    }

    private static int max(int a, int b, int c) {
        if (a > b) return a > c ? a : c;
        else return b > c ? b : c;
    }

    /**
     * 三重循环，太慢了
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSumFor3(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 0) return result;
        Set<String> same = new HashSet();
        for (int i = 0; i <= nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                int want = -nums[i] - nums[j];
                for (int x = j + 1; x < nums.length; x++) {
                    if (nums[x] == want) {//如果找到了
                        String key = min(nums[i], nums[j], nums[x]) + "-" + max(nums[i], nums[j], nums[x]);
                        if (!same.contains(key)) {
                            same.add(key);
                            List<Integer> integers = new ArrayList<>();
                            integers.add(nums[i]);
                            integers.add(nums[j]);
                            integers.add(nums[x]);
                            result.add(integers);
                        }
                        break;
                    }
                }
            }
        }
        return result;
    }

    /**
     * 使用排序
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSumBySort(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 0) return result;
        int[] sortedNum = ascSort(nums);
        //找到第一个0或者正数，从第一个0或者正数开始遍历
        int start = 0;
        for (; start < sortedNum.length; start++) {
            if (sortedNum[start] >= 0) {
                break;
            }
        }
        Set<String> same = new HashSet();
        for (int i = 0; i <= start; i++) {
            for (int j = i + 1; j < sortedNum.length - 1; j++) {
                int want = -sortedNum[i] - sortedNum[j];
                for (int x = start > j + 1 ? start : j + 1; x < sortedNum.length; x++) {
                    if (sortedNum[x] == want) {//如果找到了
                        if (!same.contains(sortedNum[i] + "-" + sortedNum[j])) {
                            same.add(sortedNum[i] + "-" + sortedNum[j]);
                            List<Integer> integers = new ArrayList<>();
                            integers.add(sortedNum[i]);
                            integers.add(sortedNum[j]);
                            integers.add(sortedNum[x]);
                            result.add(integers);
                        }
                        break;
                    } else if (sortedNum[x] > want) {
                        break;
                    }
                }
            }
        }

        return result;
    }

    /**
     * 从小到大排序
     *
     * @param nums
     * @return
     */
    public static int[] ascSort(int[] nums) {
        return sort(nums, 0, nums.length - 1);
    }

    /**
     * 递归排序
     *
     * @param nums
     * @param begin
     * @param end
     * @return
     */
    public static int[] sort(int[] nums, int begin, int end) {
        //记录基准
        int key = nums[begin];
        int last = begin;
        //记录反向
        boolean goRight = false;
        int right = begin, left = end;
        for (; right <= left; ) {
            if (goRight) {
                if (nums[right] > key) {//如果找到了比基准key大的
                    nums[last] = nums[right];
                    last = right;
                    goRight = !goRight;
                }
                right++;
            } else {
                if (nums[left] < key) {//如果找到了比基准key小的
                    nums[last] = nums[left];
                    last = left;
                    goRight = !goRight;
                }
                left--;
            }
        }
        nums[last] = key;
        //递归
        if (last - begin > 1) {
            nums = sort(nums, begin, last - 1);
        }
        if (end - last > 1) {
            nums = sort(nums, last + 1, end);
        }
        return nums;
    }

    /**
     * 使用排序和map
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 0) return result;
        //Arrays.sort(nums);之后可以用这个排序
        int[] sortedNum = ascSort(nums);
        //去重数组
        Set<String> same = new HashSet();
        //map的映射
        Map<Integer, Integer> numMap = new HashMap<>();
        //找到第一个0或者正数，从第一个0或者正数开始遍历
        int start = 0;
        for (int i = 0; i < sortedNum.length; i++) {
            if (sortedNum[i] >= 0 && start == 0) {
                start = i;
            }
            numMap.put(sortedNum[i], i);
        }
        for (int i = 0; i <= start; i++) {
            for (int j = i + 1; j < sortedNum.length - 1; j++) {
                int want = -sortedNum[i] - sortedNum[j];
                if (numMap.containsKey(want) && numMap.get(want) > j) {//如果找到了
                    if (!same.contains(sortedNum[i] + "-" + sortedNum[j])) {
                        same.add(sortedNum[i] + "-" + sortedNum[j]);
                        List<Integer> integers = new ArrayList<>();
                        integers.add(sortedNum[i]);
                        integers.add(sortedNum[j]);
                        integers.add(want);
                        result.add(integers);
                    }
                }
            }
        }
        return result;
    }


}